package CH01数组结构.LeetCode单调队列;

import java.util.Deque;
import java.util.LinkedList;

public class LC1696 {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> queue = new LinkedList<>();
        queue.offerLast(0);
        int[] f = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            while (!queue.isEmpty() && i - queue.peekFirst() > k) {
                queue.pollFirst();
            }
            f[i] = nums[i] + f[queue.peekFirst()];
            while (!queue.isEmpty() && f[i] >= f[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return f[n - 1];
    }
}